package 每日一题;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.TreeMap;

public class No456_132模式 {

    /**
     * 给你一个整数数组 nums ，数组中共有 n 个整数。
     * 132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，
     * 并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
     * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
     * 进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，
     * 你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？
     *
     * 示例 1：
     * 输入：nums = [1,2,3,4]
     * 输出：false
     * 解释：序列中不存在 132 模式的子序列。
     * 示例 2：
     * 输入：nums = [3,1,4,2]
     * 输出：true
     * 解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
     * 示例 3：
     * 输入：nums = [-1,3,2,0]
     * 输出：true
     * 解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
     *  
     * 提示：
     * n == nums.length
     * 1 <= n <= 104
     * -109 <= nums[i] <= 109
     */

    //最优解法:反向单调栈
    public boolean find132pattern(int[] nums) {

        if(nums.length<3){
            return false;
        }

        Deque<Integer> stack=new ArrayDeque<>();

        //维护次大的Num k
        int secondaryMaxNum=Integer.MIN_VALUE;

        for (int i = nums.length-1; i >= 0; i--) {

            if(nums[i]<secondaryMaxNum){
                return true;
            }

            //中间大的已经出现
            while (!stack.isEmpty()&&stack.peekLast()<nums[i]){
                //while贪心得到最大
                secondaryMaxNum=Math.max(secondaryMaxNum,stack.pollLast());
            }

            stack.addLast(nums[i]);

        }


        return false;
    }

    //直接暴力先行 N^2 可通过,维护一个minNum即可
    private boolean method0(int[] nums){
        if(nums.length<3){
            return false;
        }
        int minNum=nums[0];
        for (int i = 1; i < nums.length - 2; i++) {
            for (int j = i+1; j < nums.length - 1; j++) {
                if(minNum<nums[j]&&nums[i]>nums[j]){
                    return true;
                }
            }
            minNum=Math.min(minNum,nums[i]);
        }

        return false;
    }

    //N log N 红黑树解法,保存右边的数
    private boolean method1(int[] nums) {

        if(nums.length<3){
            return false;
        }

        TreeMap<Integer,Integer> treeMap=new TreeMap<>();

        for (int i = 1; i < nums.length; i++) {
            treeMap.put(nums[i],treeMap.getOrDefault(nums[i],0)+1);
        }

        int leftMin=nums[0];

        //开始遍历了
        for (int i = 1; i < nums.length; i++) {

            //当前元素出列,则维护一下treeMap
            Integer oldValue = treeMap.put(nums[i], treeMap.get(nums[i]) - 1);
            if(oldValue==1){
                treeMap.remove(nums[i]);
            }
            //答案可能存在
            if(leftMin<nums[i]){
                //从treeMap中找到一个比当前元素小(也是最大)的元素
                Integer integer = treeMap.lowerKey(nums[i]);
                if(integer!=null&&leftMin<integer){
                    return true;
                }
            }

            leftMin=Math.min(leftMin,nums[i]);
        }

        return false;
    }

    public static void main(String[] args) {
        No456_132模式 n=new No456_132模式();
        int[] arr={1,0,1,-4,-3};
        boolean result = n.method1(arr);
        System.out.println(result);
    }

}
